// medianfilter.h

#ifndef MEDIANFILTER_H
#define MEDIANFILTER_H

#include <stdlib.h>
#include <filter.h>

namespace {
template<typename T>
int compare(const void *a, const void *b) {
	return *(T *)a - *(T *)b;
}
}

template<typename T>
class MedianFilter : public Filter<T> {
public:
	MedianFilter(int size, T initial, T *sorted)
		: size_(size)
		, pos_(0)
		, sorted_(sorted)
		, ownsorted_(false)
	{
		init(initial);
	}

	MedianFilter(int size, T initial)
		: size_(size)
		, pos_(0)
		, sorted_(new T[size])
		, ownsorted_(true)
	{
		init(initial);
	}

	virtual ~MedianFilter() {
		if (ownsorted_)
			delete[] sorted_;
	}

	virtual T update(T value) {
		values_[pos_] = value;
		if (++pos_ >= size_)
			pos_ = 0;
			
		memcpy(sorted_, values_, size_ * sizeof(T));
		qsort(sorted_, size_, sizeof(T), compare<T>);
		return sorted_[size_ / 2];
	}

	virtual T operator()() {
		return sorted_[size_ / 2];
	}

	virtual void set(T value) {}
			
private:
	MedianFilter();

	void init(T initial) {
		for (int i = 0; i < size_; ++i)
			values_[i] = initial;
	}

	const int size_;
	int pos_;
	T *sorted_;
	bool ownsorted_;
	T *values_;
};

#endif
